The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
In a straight-line drawing of a graph, each edge is drawn as a straight-line segment. In other types of drawings, a bend appears in the edges of one or more line segments; such drawings include polyline drawings, orthogonal drawings, grid drawings, etc. Straight-line drawings are used in a variety of technical contexts. One technical context pertinent to this disclosure involves the use of a straight-line drawing to represent the topology of a computer network in a graphical display generated by a network management software application or network management system (NMS).
A graph in which all relative positions of vertices are allowed may be termed a “loosely configurable” graph. Graphs that do not allow all such positions may be termed “constrained configuration” graphs.
In present approaches for straight-line graph drawing, problems arise in the context of updating and re-drawing the graph when nodes are added to the graph or removed from it. For example, assume that at some time t1, the set of vertices in a graph V is V=V1, and for each vertex v in V its coordinate in the plane is (x(v, t1), y(v, t1)). At a later time t2, both a set of vertices V2 and a set of edges E2 are added to the graph. Accordingly, the updated graph is:                G(V, E):=G(V1+V2, E1+E2).Computer software or hardware, under program control, is used to determine new coordinate positions (x(v, t2), y(v, t2)) for each vertex v in V. However, past approaches sometimes produce results that cause cognitive disruption in viewing a redrawn graph with updated vertex positions. In particular, in certain approaches the new coordinate positions may result in drawing having lines and vertices that are not well aligned with prior coordinate positions.        
The graph drawings described herein are provided for human viewing and analysis; therefore, the criteria that determine a desirable vertex repositioning are, to a great extent, psychological in nature. Thus, it is probably impossible to claim that any given repositioning is objectively better than another, but there is a need for an algorithm that produces more reasonable results than existing approaches.
This problem is addressed in the subject of chapter 7 of Di Battista et al., “Graph Drawing: algorithms for the visualization of graphs” (New Jersey: Prentice Hall, ISBN: 0-13-301615-3). The authors observe: “If an insertion or deletion operation is performed on the graph, then the new graph should be redrawn. Running any drawing algorithm on the new graph will result in a new drawing, which may be vastly different from the previous one. The user may need to spend considerable cognitive effort in trying to relate the new drawing to the previous one . . . This dramatic change destroys the user's ‘mental map’, that is, the mental image of the drawing . . . ” Di Battista et al. state that models for the mental map, as well as some layout adjustment methods which preserve the mental map, are introduced in Misue et al., Layout adjustment and the Mental Map, J. Visual Lang. Comput., 6, no. 2, 183-210, 1995.
These issues become acute, for example, when nodes or other elements of the graph appear to “jump” in relative or absolute position after an update to the drawing. In redrawing a graph, Di Battista et al. describe four general approaches. In the “no-change scenario” approach, “the coordinates of the already placed vertices, bends and edges do not change at all . . . In this scenario, the user's mental map is strongly preserved.”
Thus, there is a need for an approach that minimizes the cognitive effort needed to contemplate a new drawing in comparison to a previous one. In the specific context of network management systems, there is a need for a way to redraw straight-line graphs used for network topology displays in a manner that minimizes the cognitive effort needed to relate an updated display to a previous display.